#include"linear.h"

void ht_init (HashTable **pp_ht, int m, int p)
{
	(*pp_ht) = (HashTable *)malloc(sizeof(HashTable));
	(*pp_ht)->elem_num = 0;
	(*pp_ht)->m = m;
	(*pp_ht)->p = p;
	
	int i;
	for (i = 0; i < TABLE_SIZE; ++i) {
		(*pp_ht)->table[i].key = NULLKEY;
		(*pp_ht)->table[i].count = 0;
	}
}

void ht_print (HashTable *ht)
{
	int i;
	printf("hash table :\n");
	for (i = 0; i < TABLE_SIZE; ++i)
		printf(" %d", ht->table[i].key);
	printf("\n");
}

void ht_destroy (HashTable *ht)
{
	free(ht);
}

bool ht_insert (HashTable *ht, KeyType k)
{
	int adr;
	adr = k % ht->p;
	
	if (ht->elem_num == TABLE_SIZE)
		return false;
	
	if (ht->table[adr].key == NULLKEY || ht->table[adr].key == DELKEY) {
		
		ht->table[adr].key = k;
		ht->table[adr].count = 1;

	} else {
		
		int i = 1;
		do {
			adr = (adr + 1) % ht->p;
			++i;
		} while (ht->table[adr].key != NULLKEY &&
				 ht->table[adr].key != DELKEY);
		ht->table[adr].key = k;
		ht->table[adr].count = i;

	}
	ht->elem_num += 1;
	return true;

}

void ht_create (HashTable *ht, KeyType *keys, int n)
{
	int i;
	for (i = 0; i < n; ++i)
		ht_insert(ht, keys[i]);
}

bool ht_delete (HashTable *ht, KeyType k)
{
	if (ht->elem_num == 0)
		return false;
	
	int count = 1, adr;
	adr = k % ht->p;

	while (count <= TABLE_SIZE && ht->table[adr].key != NULLKEY &&
			ht->table[adr].key != k) {
		adr = (adr + 1) % ht->p;
		++count;
	}
	
	if (count > TABLE_SIZE || ht->table[adr].key == NULLKEY) {
		return false;
	} else {
		ht->table[adr].key = DELKEY;
		ht->table[adr].count = 0;
		ht->elem_num -= 1;
		return true;
	}
		
}

void ht_search (HashTable *ht, KeyType k)
{
	if (ht->elem_num == 0) {
		printf("table is empty.\n");
		return ;
	}

	int count = 1, adr;
	adr = k % ht->p;
	
	while (count <= TABLE_SIZE && ht->table[adr].key != NULLKEY &&
			ht->table[adr].key != k) {
		adr = (adr + 1) % ht->p;
		++count;
	}

	if (count > TABLE_SIZE || ht->table[adr].key == NULLKEY) {
		printf("the key %d is not exist in hash table.\n", k);
	} else {
		printf("search key %d need %d times comparation.\n", k, count);
	}
}

void ASL (HashTable *ht)
{
	int i, sum;
	
	for (i = sum = 0; i < TABLE_SIZE; ++i)
		if (ht->table[i].key != NULLKEY && ht->table[i].key != DELKEY)
			sum += ht->table[i].count;
	printf("ASL of success is %.2f\n"
			"key total: %d\n", sum * 1.0 / ht->elem_num, ht->elem_num);
}
